package leetcode_100;

import java.util.Stack;

public class InterleavingString_97 {

	public static void main(String[] args) {
		InterleavingString_97 test=new InterleavingString_97();
		System.out.println(test.isInterleave1("aabcc","dbbca","aadbbcbcac"));
		System.out.println(test.isInterleave1("aabcc","dbbca","aadbbbaccc"));
		System.out.println(test.isInterleave1("","",""));
		System.out.println(test.isInterleave1("abc","","abc"));
		System.out.println(test.isInterleave1("aabaac","aadaaeaaf","aadaaeaabaafaac"));

	}
	
	/**
	 * describe:用栈保存回退数组 思想正确 但是超时了
	 * 2018年5月19日 下午2:47:33
	 */
	public boolean isInterleave(String s1, String s2, String s3) {
		int length1=s1.length();
		int length2=s2.length();
        if(length1+length2!=s3.length())
        	return false;
        else {
        	int index1=0,index2=0,index3=0;
        	Stack<Integer> back=new Stack<Integer>();
        	Stack<Integer> back1=new Stack<Integer>();
        	Stack<Integer> back2=new Stack<Integer>();
        	while(index3<s3.length()) {
        		char now=s3.charAt(index3);
        		if(index1==length1) {//s1已经比完
        			if(s3.substring(index3).equals(s2.substring(index2)))
        				return true;
        			else if(!back.isEmpty()) {//回退
        				index2=back2.pop()+1;
            			index1=back1.pop();
            			index3=back.pop()+1;
            			continue;
        			}
        			return false;
        		}
        		
        		if(index2==length2) {//s1已经比完
        			if(s3.substring(index3).equals(s1.substring(index1)))
        				return true;
        			else if(!back.isEmpty()) {//回退
        				index2=back2.pop()+1;
            			index1=back1.pop();
            			index3=back.pop()+1;
            			continue;
        			}
        			return false;
        		}
        		
        	   char c1=s1.charAt(index1),c2=s2.charAt(index2);
        		if(c1==now) {
        			if(c2==now) {//做回退标记
        				back1.push(index1);
        				back2.push(index2);
        				back.push(index3);
        				++index1;//先让index1走
        				++index3;
        				continue;
        			}
        			else {
        				index1++;
        				++index3;
        				continue;
        			}
        		}
        		if(c2==now) {//此时c1已经不等于now了
        			index2++;
        			++index3;
        			continue;	
        		}
        		if(!back.isEmpty()) {//此时c1 和c2都不等于now 有回退选项
        			index2=back2.pop()+1;//让index2走
        			index1=back1.pop();
        			index3=back.pop()+1;
        			continue;
        		}
        		return false;
        	}
        }
		return true;
    }
	
	
	
	 /**
	 * describe: 考虑动态规划 AC 7%
	 * 2018年5月19日 下午3:05:56
	 * dp[i][j] 表示 s2 的前 i 个字符和 s1 的前 j 个字符是否匹配 s3 的前 i+j 个字符。
	 * 初始化dp[0][0]=0，dp[0][j]表示s2取0个，即s1的前j个字符是否匹配s3的前j个字符；
	 * dp[i][0]表示s1取0个，即s2的前i个字符，是否匹配s3的前i个字符。
	动规方程：dp[i][j] = dp[i - 1][j] && s2[i - 1] == s3[i + j - 1]  ||  dp[i][j - 1] && s1[i][j - 1] == s3[i + j - 1] ，
	意思是如果s2的前i-1个字符和s1的前j个字符已经和s3的前i+j-1个字符匹配且s2的第i个字符等于s3的第i+j个字符，
	或者s2的前i个字符和s1的前j-1个字符已经和s3的前i+j-1个字符匹配，
	且s1的第j个字符等于s3的第i+j个字符，那么s2的前i个字符和s1的前j个字符能否与s3的前i+j-1个字符匹配
	 */
	public boolean isInterleave1(String s1, String s2, String s3) {
		    int length1 = s1.length();
	        int length2 = s2.length();
	        if(length1+length2!=s3.length())
	            return false;
	        boolean dp[][]=new boolean[length1+1][length2+1];
	        for(int i = 0; i < length1+1; i ++)
	        {
	            for(int j = 0; j < length2+1; j ++)
	            {
	                if(i == 0 && j == 0)//才开始
	                    dp[i][j] = true;
	                else if(i == 0)
	                    dp[i][j] = dp[i][j-1] & (s2.charAt(j-1)==s3.charAt(j-1));
	                else if(j == 0)
	                    dp[i][j] = dp[i-1][j] & (s1.charAt(i-1)==s3.charAt(i-1));
	                else
	                    dp[i][j] = (dp[i][j-1] & (s2.charAt(j-1)==s3.charAt(i+j-1))) || (dp[i-1][j] & (s1.charAt(i-1)==s3.charAt(i+j-1)));
	            }
	        }
	        return dp[length1][length2];
	 }

}
